#include "config.h"

#include <stdint.h>
#include <errno.h>

#define DBG_SUBSYS S_LIBYLIB

#include "hash_table.h"
#include "sysy_lib.h"
#include "mem_pool.h"
#include "dbg.h"

#define INIT_HASH_TABLE_SIZE  (65535)
#define RING_POOL_MAX_SIZE    INIT_HASH_TABLE_SIZE
#define HASH_TABLE_RESIZE_NUM 2

static int ymalloc_malloc(void **ptr, size_t size, void *ctx) {
        (void) ctx;
        return ymalloc(ptr, size);
}

static int ymalloc_free(void **ptr, void *ctx) {
        (void) ctx;
        return yfree(ptr);
}

static int pool_malloc(void **ptr, size_t size, void *ctx) {
        (void) size;
        hashtable_t t = ctx;
        return ring_pool_pop(t->ring_pool, ptr, 1);
}

static int pool_free(void **ptr, void *ctx) {
        if (likely(*ptr != NULL)) {
                hashtable_t t = ctx;
                ring_pool_push(t->ring_pool, ptr, 1);
                *ptr = NULL;
        } else {
                YASSERT(0);
        }
        return 0;
}

/**
 * a very simple hash table implementation with paramerterizable
 * comparison and key generation functions. it does resize
 * in order to accomidate more entries, and collapses
 * the table to free unused memory
 */
/*uint32_t key_from_str(char *s)
{
        return hash_str(s);
}*/

static hashtable_entry_t *hashtable_lookup(hashtable_t t, const void *comparator, uint32_t k,
                                     int (*compare_func)(const void *, const void *),
                                     int *success)
{
        uint32_t key = k % t->size;
        hashtable_entry_t *i;

        for (i = &(t->entries[key]); *i; i = &((*i)->next)) {
                if (compare_func && (*i)->key == k  && (*t->compare_f)((*i)->value, comparator) == 0) {
                        *success = 1;
                        return i;
                }
        }

        *success = 0;

        return &(t->entries[key]);
}

int hashtable_resize(hashtable_t t, int size)
{
        int ret, old_size, i, success;
        uint32_t len;
        void *ptr;
        hashtable_entry_t *old_entries, entry, next, *position;

        len = sizeof(hashtable_entry_t) * size;

        if(likely(t->alloc_type == HTABLE_ALLOC_HUGE)) {
                ret = huge_malloc(&ptr, len);
        }
        else
                ret = ymalloc(&ptr, len);
        if (unlikely(ret))
                GOTO(err_ret, ret);

        memset(ptr, 0, len);

        old_size = t->size;
        old_entries = t->entries;

        t->size = size;
        t->entries = (hashtable_entry_t *)ptr;

        for (i = 0; i < old_size; i++) {
                for (entry = old_entries[i]; entry; entry = next) {
                        next = entry->next;
                        position = hashtable_lookup(t, 0, entry->key, 0, &success);
                        entry->next = *position;
                        *position = entry;
                }
        }

        if(likely(t->alloc_type == HTABLE_ALLOC_HUGE))
                huge_free((void **)&old_entries);
        else
                yfree((void **)&old_entries);

        if (size > 1024)
                DINFO("resize %s, new size %u\n", t->name, size);

        return 0;
err_ret:
        return ret;
}

/**
 * Function: hash_create_table
 * Arguments: compare_function: a function to compare
 *                              a table instance with a correlator
 *            key_function: a function to generate a 32 bit 
 *                          hash key from a correlator
 * Returns: a pointer to the new table or null
 */
hashtable_t hash_create_table2(compare_func compare_f, key_func key_f, const char *name, int alloc_type)
{
        int ret;
        uint32_t len;
        void *ptr;
        hashtable_t new;

        len = sizeof(struct hashtable);

        if(likely(alloc_type == HTABLE_ALLOC_HUGE))
                ret = huge_malloc(&ptr, len);
        else
                ret = ymalloc(&ptr, len);

        if (unlikely(ret))
                GOTO(err_ret, ret);

        memset(ptr, 0, len);
        new = (hashtable_t)ptr;

        len = sizeof(hashtable_entry_t) * INIT_HASH_TABLE_SIZE;

        if(likely(alloc_type == HTABLE_ALLOC_HUGE))
                ret = huge_malloc(&ptr, len);
        else
                ret = ymalloc(&ptr, len);
        if (unlikely(ret))
                GOTO(err_table, ret);

        memset(ptr, 0, len);

        strncpy(new->name, name, MAX_NAME_LEN);
        new->size = INIT_HASH_TABLE_SIZE;
        new->num_of_entries = 0;
        new->entries = (hashtable_entry_t *)ptr;
        new->compare_f = compare_f;
        new->key_f = key_f;
        new->alloc_type = alloc_type;

        new->ring_pool = NULL;

        if (alloc_type == HTABLE_ALLOC_YMALLOC) {
                new->entry_malloc_f = ymalloc_malloc;
                new->entry_free_f = ymalloc_free;
        } else if (alloc_type == HTABLE_ALLOC_HUGE) {
                // TODO
                new->ring_pool = ring_pool_create("htable", RING_POOL_MAX_SIZE, sizeof(struct hashtable_entry));
                YASSERT(new->ring_pool != NULL);

                new->entry_malloc_f = pool_malloc;
                new->entry_free_f = pool_free;
        } else {
                YASSERT(0);
        }

        return new;
err_table:
        if(likely(new->alloc_type == HTABLE_ALLOC_HUGE))
                huge_free((void **)&new);
        else
                yfree((void **)&new);
err_ret:
        return NULL;
}

hashtable_t hash_create_table(compare_func compare_f, key_func key_f, const char *name)
{
        return hash_create_table2(compare_f, key_f, name, HTABLE_ALLOC_YMALLOC);
}

hashtable_t hash_create_table_huge(compare_func compare_f, key_func key_f, const char *name)
{ 
        return hash_create_table2(compare_f, key_f, name, HTABLE_ALLOC_HUGE);
}
/**
 * Function: hash_table_find
 * Arguments: t: a table to look in
 *            comparator: a value to access the table entry
 * Returns: the element references to by comparator, or null
 */
void *hash_table_find(hashtable_t t, const void *comparator)
{
        int success;
        hashtable_entry_t *entry;

        entry = hashtable_lookup(t, comparator, (*t->key_f)(comparator),
                                 t->compare_f, &success);

        if (success)
                return (*entry)->value;

        return NULL;
}

/**
 * Function: hash_table_insert
 * Arguments: t: a table to insert the object
 *            value: the object to put in the table
 *            comparator: the value by which the object 
 *                        will be addressed
 * Returns: 0 or errno
 */
int hash_table_insert(hashtable_t t, void *value, void *comparator, int overwrite)
{
        int ret, success;
        uint32_t k, len;
        hashtable_entry_t *position, entry;
        void *ptr;

        YASSERT(value);

        k = (*t->key_f)(comparator);

        position = hashtable_lookup(t, comparator, k, t->compare_f, &success);

        if (success) {
                if (!overwrite) {
                        ret = EEXIST;
                        GOTO(err_ret, ret);
                }

                entry = *position;
                if(likely(t->alloc_type == HTABLE_ALLOC_HUGE))
                        huge_free((void **)&entry->value);
                else
                        yfree((void **)&entry->value);
        } else {
                len = sizeof(struct hashtable_entry);

                ret = t->entry_malloc_f(&ptr, len, t);
                if (unlikely(ret))
                        GOTO(err_ret, ret);

                entry = (hashtable_entry_t)ptr;

                entry->next = *position;
                *position = entry;

                t->num_of_entries++;
        }

        entry->value = value;
        entry->key = k;

        if (t->num_of_entries > t->size)
                (void) hashtable_resize(t, t->size * HASH_TABLE_RESIZE_NUM);

        return 0;
err_ret:
        return ret;
}

/**
 * Function: hash_table_remove
 * Arguments: t: the table to remove the object from
 *            comparator: the index value of the object to remove
 * Returns: 0 or ENOENT
 */
int hash_table_remove(hashtable_t t, const void *comparator, void **value)
{
        int success;
        hashtable_entry_t *position, entry;

        position = hashtable_lookup(t, comparator, (*t->key_f)(comparator),
                                t->compare_f, &success);

        if (!success)
                return ENOKEY;

        entry = *position;
        *position = entry->next;

        if (value)
                *value = entry->value;
        else {
                if(likely(t->alloc_type == HTABLE_ALLOC_HUGE))
                        huge_free(&entry->value);
                else
                        yfree((void **)&entry->value);
        }
               

        t->entry_free_f((void **)&entry, t);

        t->num_of_entries--;

#if 0
        if (t->num_of_entries < t->size / HASH_TABLE_RESIZE_NUM)
                (void) hashtable_resize(t, t->size / HASH_TABLE_RESIZE_NUM);
#endif

        return 0;
}

/**
 * Function: hash_iterate_table_entries
 * Arguments: t: the table to iterate over
 *            handler: a function to call with each element
 *                     of the table, along with arg
 *            arg: the opaque object to pass to handler
 * Returns: nothing
 */
int hash_iterate_table_entries(hashtable_t t, int (*handler)(void *, void *),
                                void *arg)
{
        int ret;
        unsigned int i;
        hashtable_entry_t entry, next;

        for (i = 0; i < t->size; i++) {
                for (entry = t->entries[i]; entry; entry = next) {
                        next = entry->next;

                        ret = (*handler)(arg, entry->value);
                        if (unlikely(ret))
                                GOTO(err_ret, ret);
                }
        }

        return 0;
err_ret:
        return ret;
}

/**
 * Function: hash_filter_table_entries
 * Arguments: t: the table to iterate over
 *            handler: a function to call with each element
 *                     of the table, along with arg
 *            arg: the opaque object to pass to handler
 * Returns: nothing
 * Notes: operations on the table inside handler are not safe
 *
 * filter_table_entires() calls the handler function for each
 *   item in the table, passing it and arg. The handler function
 *   returns 1 if it is to be retained in the table, and 0
 *   if it is to be removed.
 */
void hash_filter_table_entries(hashtable_t t, int (*handler)(void *, void *),
                               void *arg, void (*thunk)(void *))
{
        unsigned int i;
        hashtable_entry_t *j, *next, entry;

        for (i = 0; i < t->size; i++)
                for (j = t->entries + i; *j; j = next) {
                        next = &((*j)->next);

                        if (!(*handler)(arg, (*j)->value)) {
                                next = j;

                                entry = *j;
                                *j = (*j)->next;

                                if (thunk)
                                        (*thunk)(entry->value);

                                t->entry_free_f((void **)&entry, t);

                                t->num_of_entries--;

                                if (t->num_of_entries
                                    < t->size / HASH_TABLE_RESIZE_NUM)
                                        (void) hashtable_resize(t,
                                               t->size / HASH_TABLE_RESIZE_NUM);
                        }
                }
}

/**
 * Function: destroy_table
 * Arguments: t: the table to free
 *            thunk: a function to call with each element,
 *                   most likely free()
 * Returns: nothing
 */
void hash_destroy_table(hashtable_t t, void (*thunk)(void *))
{
        unsigned int i;
        hashtable_entry_t entry, next;

        YASSERT(t);

        for (i = 0; i < t->size; i++) {
                for (entry = t->entries[i]; entry; entry = next) {
                        next = entry->next;

                        if (thunk)
                                (*thunk)(entry->value);
                        else {
                                if(likely(t->alloc_type == HTABLE_ALLOC_HUGE))
                                        huge_free((void **)&entry->value);
                                else
                                        yfree((void **)&entry->value);
                        }

                        t->entry_free_f((void **)&entry, t);
                }
        }

        if (t->ring_pool) {
                ring_pool_free(t->ring_pool);
                t->ring_pool = NULL;
        }

        if(likely(t->alloc_type == HTABLE_ALLOC_HUGE)) {
                huge_free((void **)&t->entries);
                huge_free((void **)&t);
        }
        else {
                yfree((void **)&t->entries);
                yfree((void **)&t);
        }
}
